package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

/**
 * @author By ZengPeng
 */
public class 力扣_695_岛屿的最大面积 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_695_岛屿的最大面积().
                maxAreaOfIsland(new int[][]{{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}}
        ));
    }

    /**
    题目：给你一个大小为 m x n 的二进制矩阵 grid 。
     岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。
     你可以假设 grid 的四个边缘都被 0（代表水）包围着。
     岛屿的面积是岛上值为 1 的单元格的数目。
     计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。


     示例 1：
     输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
     输出：6
     解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
     示例 2：

     输入：grid = [[0,0,0,0,0,0,0,0]]
     输出：0

    分析：【P ❤🧡💛💙】
       1.递归：位图标记已经统计过的值，避免重复计算和死循环
            优化：直接使用地图做修改记录
        --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
    边界值 & 注意点：
       1.
     **/
    public int maxAreaOfIsland(int[][] grid) {
        int max=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1 )
                    max = Math.max(max, dfs(grid,i,j));
            }
        }
        return max;
    }
    int dfs(int[][] grid, int x, int y){
        if( x <0 || x>=grid.length|| y<0||y>=grid[0].length ||  grid[x][y]==0)
            return 0;
        grid[x][y] = 0;
        int sum = dfs(grid,x-1,y);
        sum+=dfs(grid,x+1,y);
        sum+=dfs(grid,x,y-1);
        sum+=dfs(grid,x,y+1);
        return ++sum;
    }
}
